package binarytree

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	} else if key > root.Val {
		root.Right = deleteNode(root.Right, key)
	} else if key < root.Val {
		root.Left = deleteNode(root.Left, key)
	} else {
		if root.Left == nil && root.Right != nil {
			root = root.Right
		} else if root.Right == nil && root.Left != nil {
			root = root.Left
		} else if root.Right == nil && root.Left == nil {
			root = nil
		} else {
			node := root.Right
			for node.Left != nil {
				node = node.Left
			}
			node.Left = root.Left
			root = root.Right
		}
	}

	return root
}
